package com.fanshuai.algorithms.divide;

/**
 * 在一个 2^k * 2^k 个方格组成的棋盘中，有一个方格与其它的不同，若使用以下四种 L 型骨牌覆盖除这个特殊方格的其它方格，如何覆盖。
 * 四个 L 型骨牌如下图：https://blog.csdn.net/weixin_43201433/article/details/89294425
 */
public class ChessBoard {

    /**
     *  在一个 2^k * 2^k 个方格组成的棋盘中，有一个方格与其它的不同.若使用以下四种 L 型骨牌覆盖除这个特殊方格的其它方格，如何覆盖
     *
     *  分治法解决：将棋盘横竖分为4个子棋盘，分别对四个子棋盘处理：
     *  如果特殊点在子棋盘内，递归处理；如果不在，将子棋盘最里面的点（父棋盘中心四个点之一）设为特殊点，递归处理
     * @param size   棋盘大小 size为2^k
     * @param dx     棋盘特殊方格位置横坐标
     * @param dy     棋盘特殊方格位置纵坐标
     */
    public static int[][] chessBoard(int size, int dx, int dy) {
        int[][] chess = new int[size][size];
        chess[dx][dy] = -1;

        //L型骨牌序号
        int tile = 0;
        chessBoard(chess, 0, 0, dx, dy, size, tile);

        return chess;
    }

    /**
     *
     * @param chess  棋盘
     * @param startX 子棋盘起始坐标X
     * @param startY 子棋盘起始坐标Y
     * @param dx     棋盘特殊方格位置横坐标x
     * @param dy     棋盘特殊方格位置纵坐标y
     * @param size   子棋盘大小
     */
    private static void chessBoard(int[][] chess, int startX, int startY, int dx, int dy, int size, int tile) {
        if (size == 1) {
            return;
        }

        int innerX, innerY;
        size = size / 2;

        int tile0 = tile;

        //分别对四个子棋盘处理
        //左上
        if (contains(startX, startY, dx, dy, size)) {
            chessBoard(chess, startX, startY, dx, dy, size, ++tile);
        } else {
            innerX = startX + size - 1;
            innerY = startY + size - 1;
            chess[innerX][innerY] = tile0;

            chessBoard(chess, startX, startY, innerX, innerY, size, ++tile);
        }

        //右上
        if (contains(startX, startY + size, dx, dy, size)) {
            chessBoard(chess, startX, startY + size, dx, dy, size, ++tile);
        } else {
            innerX = startX + size - 1;
            innerY = startY + size;
            chess[innerX][innerY] = tile0;

            chessBoard(chess, startX, startY + size, innerX, innerY, size, ++tile);
        }

        //左下
        if (contains(startX + size, startY, dx, dy, size)) {
            chessBoard(chess, startX + size, startY, dx, dy, size, ++tile);
        } else {
            innerX = startX + size;
            innerY = startY + size - 1;
            chess[innerX][innerY] = tile0;

            chessBoard(chess, startX + size, startY, innerX, innerY, size, ++tile);
        }

        //右下
        if (contains(startX + size, startY + size, dx, dy, size)) {
            chessBoard(chess, startX + size, startY + size, dx, dy, size, ++tile);
        } else {
            innerX = startX + size;
            innerY = startY + size;
            chess[innerX][innerY] = tile0;

            chessBoard(chess, startX + size, startY + size, innerX, innerY, size, ++tile);
        }
    }

    /**
     * 特殊点是否在子棋盘内
     * @param startX
     * @param startY
     * @param dx
     * @param dy
     * @param size
     * @return
     */
    private static boolean contains(int startX, int startY, int dx, int dy, int size) {
        return dx >= startX && dx <= startX + size - 1 && dy >= startY && dy <= startY + size - 1;
    }

    public static void main(String[] args) {
        int[][] chess = chessBoard(8, 3, 2);
        for (int i = 0; i < chess.length; i++) {
            for (int j = 0; j < chess[0].length; j++) {
                System.out.print(chess[i][j] + " ");
            }
            System.out.println();
        }
    }
}
